<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /**
         * 
         * 两个字符串的删除操作
         * 给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。
           输入：word1 = "sea", word2 = "eat"
           输出：2
           解释：第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"

           输入：word1 = "leetcode", word2 = "etco"
           输出：4
           解释：第一步将'leetcode' 变为'eetcode',第二步：'eetcode'变为'etcode'，第三步：'etcode'变为'etcod',第四步：'etcod'变为'etco'

           分析：
        */
        /* 
            时间：
            空间：
        */
        // 递归解法
        var minDistance = function(word1, word2) {
            let word1Len = word1.length;
            let word2Len = word2.length;
            const helper = (i, j) => {
                if (i < 0) {
                    return 0
                } 
                if (j < 0) {
                    return 0
                }

                if (word1[i] === word2[j]) {
                    return helper(i - 1, j - 1) + 1
                } else {
                    return Math.max(helper(i - 1, j), helper(i, j - 1))
                }

            }
            const res = helper(word1Len - 1, word2Len - 1)
            // 上面所有的思路都是最长公共子序列，除了最后return
            return (word1.length - res) + (word2.length - res)
        };
        console.log(minDistance('leetcode', 'etco'));
        console.log(minDistance('sea', 'eat'));
    </script>
</body>

</html>